package com.xyhuo.leetcode.y2025;

import com.xyhuo.leetcode.common.TreeNode;

public class LowestCommonAncestor {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        int search = search(root, p, q);
        if (search == 1) {
            return p;
        } else if (search == 2) {
            return q;
        }
        return ans;
    }

    private TreeNode ans = null;

    private int search(TreeNode root, TreeNode p, TreeNode q) {
        if (null == root || null != ans) {
            return 0;
        }
        int fp = search(root.left, p, q);
        if (root.val == p.val) {
            return 1;
        }
        if (root.val == q.val) {
            return 2;
        }
        int fq = search(root.right, p, q);

        if (fp + fq == 3 && ans == null) {
            ans = root;
        }
        return fp + fq;
    }

    public static void main(String[] args) {
        TreeNode t0 = new TreeNode(0);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);
        TreeNode t4 = new TreeNode(4);
        TreeNode t5 = new TreeNode(5);
        TreeNode t6 = new TreeNode(6);
        TreeNode t7 = new TreeNode(7);
        TreeNode t8 = new TreeNode(8);
        TreeNode t9 = new TreeNode(9);
        t2.left = t0;
        t2.right = t4;
        t4.left = t3;
        t4.right = t5;
        t6.left = t2;
        t6.right = t8;
        t8.left = t7;
        t8.right = t9;
        LowestCommonAncestor l = new LowestCommonAncestor();
        l.lowestCommonAncestor(t6, t2, t8);


    }
}
